//
// Created by Snow on 2023/4/21.
//
//拓扑排序
#include"graph0.cpp"
#include"../Lesson3/SqStack.cpp"
void TopSort(AdjGraph *G)
{
    SqStack *st;//定义一个栈，元素类型为int类型
    InitStack(st);//初始化栈
    int indegree[MAXV];//定义一个入度数组
    for(int i=0;i<G->n;i++)
        indegree[i]=0;
    for(int i=0;i<G->n;i++)//求所有顶点的入度
    {
        ArcNode *p=G->adjlist[i].firstarc;
        while(p!=nullptr)
        {
            int w=p->adjvex;//找到顶点i的邻接点w
            indegree[w]++;//顶点w的入度加1
            p=p->nextarc;
        }
    }
    for(int i=0;i<G->n;i++)//将入度为0的顶点进栈
    {
        if(indegree[i]==0)
            Push(st,i);
    }
    int i;
    while(!StackEmpty(st))//栈不为空时循环
    {
        Pop(st,i);//将一个顶点i出栈
        printf("%d ",i);//输出该顶点
        ArcNode *p=G->adjlist[i].firstarc;//寻找第一个邻接点
        while(p!=nullptr)//将顶点i的出边邻接点的入度减一
        {
            int w=p->adjvex;//存在边<i,w>中
            indegree[w]--;//顶点w的入度减一
            if(indegree[w]==0)//将入度为0的邻接点w进栈
                Push(st,w);
            p=p->nextarc;//找下一个邻接点
        }
    }
}
int main()
{
    AdjGraph *G;
    int A[MAXV][MAXV]=
            {{0,1,INF,INF,INF,INF},
             {INF,0,1,INF,INF,INF},
             {INF,INF,0,1,INF,INF},
             {INF,INF,INF,0,INF,INF},
             {INF,1,INF,INF,0,1},
             {INF,INF,INF,1,INF,0}};
    int n=6, e=6;
    CreateAdj(G,A,n,e);			//建立《教程》中图8.44的邻接表
    printf("G:\n");
    DispAdj(G);					//输出邻接表G
    TopSort(G);
    DestroyAdj(G);				//销毁邻接表
    return 1;
}